package demo01Array;

import org.junit.Test;

/**
 * @ClassName $ {NAME}
 * @Description TODO
 * @Author shenxinyuan
 * @Date $ {DATE} $ {TIME}
 * @Version 1. 0
 **/

public class SearchInTwoDimensionArray {
    int[][] arr = {
            {1, 2, 8, 9},
            {2, 4, 9, 12},
            {4, 7, 10, 13},
            {6, 8, 11, 15}};

    /**
     * @Author shenxinyuan
     * @Description //TODO 利用二维数组从左到右，从上到下升序排列的规律；采用row++,col--的方式遍历比较时间复杂度大概为O(n+m);n是行数，
     * m是二维数组列数；空间复杂度为O(1)
     * @Date 13:15 2021/7/17
     * @Param [target, array]
     * @return boolean
     **/
    public boolean Find(int target, int[][] array) {
        int row = 0;
        int col = array[0].length - 1;
        while (row <= array.length - 1 && col >= 0) {
            if (target == array[row][col])
                return true;
            else if (target > array[row][col])
                row++;
            else
                col--;
        }
        return false;
    }


    @Test
    public void Test() {
        System.out.println("Find(8,arr) = " + Find(8, arr));
        System.out.println("Find(6,arr) = " + Find(6, arr));
    }

}